<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/dute_favicon_32x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/dute_favicon_16x16.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">
  <link rel="manifest" href="/images/manifest.json">
  <meta name="msapplication-config" content="/images/browserconfig.xml">
  <meta http-equiv="Cache-Control" content="no-transform">
  <meta http-equiv="Cache-Control" content="no-siteapp">
  <meta name="google-site-verification" content="mpI5dkydstZXl6UcDCppqktXK0bbvqdZ6LkZ3KNk4Iw">
  <meta name="baidu-site-verification" content="code-a1LksZX2Ds">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"whitestore.top","root":"/","scheme":"Gemini","version":"7.8.0","exturl":true,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":true,"scrollpercent":true},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":true,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="有问题找布隆">
<meta property="og:type" content="article">
<meta property="og:title" content="LSM-Tree - LevelDb 布隆过滤器">
<meta property="og:url" content="https://whitestore.top/2022/05/21/leveled-bloom/index.html">
<meta property="og:site_name" content="爱看书的阿东">
<meta property="og:description" content="有问题找布隆">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205031233283.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205031235855.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205031927973.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205032059650.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041413726.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041414674.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041327457.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041418134.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041423865.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041424497.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041424841.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041431847.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041431129.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041435792.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041436632.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041441884.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041219187.png">
<meta property="article:published_time" content="2022-05-21T11:07:44.000Z">
<meta property="article:modified_time" content="2023-07-16T06:28:09.225Z">
<meta property="article:author" content="阿东">
<meta property="article:tag" content="布隆过滤器">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205031233283.png">

<link rel="canonical" href="https://whitestore.top/2022/05/21/leveled-bloom/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>LSM-Tree - LevelDb 布隆过滤器 | 爱看书的阿东</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

<link rel="alternate" href="/atom.xml" title="爱看书的阿东" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">爱看书的阿东</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">赐他一块白色石头，石头上写着新名</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-fw fa-home"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-fw fa-tags"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-fw fa-th"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-fw fa-archive"></i>归档</a>

  </li>
        <li class="menu-item menu-item-sitemap">

    <a href="/sitemap.xml" rel="section"><i class="fa fa-fw fa-sitemap"></i>站点地图</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    

  <span class="exturl github-corner" data-url="aHR0cHM6Ly9naXRodWIuY29tL2xhenlUaW1lcw==" title="Follow me on GitHub" aria-label="Follow me on GitHub"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></span>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://whitestore.top/2022/05/21/leveled-bloom/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="阿东">
      <meta itemprop="description" content="随遇而安">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="爱看书的阿东">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          LSM-Tree - LevelDb 布隆过滤器
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2022-05-21 19:07:44" itemprop="dateCreated datePublished" datetime="2022-05-21T19:07:44+08:00">2022-05-21</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2023-07-16 14:28:09" itemprop="dateModified" datetime="2023-07-16T14:28:09+08:00">2023-07-16</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/LevelDB/" itemprop="url" rel="index"><span itemprop="name">LevelDB</span></a>
                </span>
            </span>

          
            <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2022/05/21/leveled-bloom/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2022/05/21/leveled-bloom/" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="fa fa-file-word-o"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>17k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="fa fa-clock-o"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>15 分钟</span>
            </span>
            <div class="post-description">有问题找布隆</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="LSM-Tree-LevelDb布隆过滤器"><a href="#LSM-Tree-LevelDb布隆过滤器" class="headerlink" title="LSM-Tree - LevelDb布隆过滤器"></a>LSM-Tree - LevelDb布隆过滤器</h1><h1 id="引言"><a href="#引言" class="headerlink" title="引言"></a>引言</h1><p>布隆过滤器有点类似哈希表，但是比哈希表的效率要更高，因为使用了位来判断Key是否存在，布隆过滤器在完成高效搜索key是否存在的同时带来一定的副作用– <strong>不保证Key一定存在</strong>，所以它只适用于允许一定容错率的系统。</p>
<p>一句话概括：<code>Bloom Filter</code> 是一个<strong>基于概率的数据结构</strong>，它只能告诉我们一个元素绝对不在集合内或<strong>可能</strong>在集合内。</p>
<p>布隆过滤器比较悬浮的东西是它不保证元素百分百在一个集合内，所以适用于具备一定容错的业务，关于它的理论和实践很多内容都是参考或者直接摘自网上的资料加上自己的理解，如有错误欢迎指正。</p>
<a id="more"></a>

<h1 id="理论"><a href="#理论" class="headerlink" title="理论"></a>理论</h1><p>理论基础相关文章都大同小异，这里归纳自这一篇大神写的文章：<span class="exturl" data-url="aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tZW5nL2FydGljbGUvZGV0YWlscy8xNDk1NTAw" title="https://blog.csdn.net/jiaomeng/article/details/1495500">Bloom Filter概念和原理_jiaomeng的博客-CSDN博客_bloomfilter<i class="fa fa-external-link"></i></span>，简洁易懂，另外建议多参考原始论文，这里很多内容其实也是归纳自老外早已写出来的论文。</p>
<p>在这个网址中可以通过JS代码查看实际的运行效果：<br><span class="exturl" data-url="aHR0cHM6Ly9sbGltbGxpYi5naXRodWIuaW8vYmxvb21maWx0ZXItdHV0b3JpYWwvemhfQ04v" title="https://llimllib.github.io/bloomfilter-tutorial/zh_CN/">Bloom Filters by Example (llimllib.github.io)<i class="fa fa-external-link"></i></span></p>
<blockquote>
<p>注意在案例中使用了<code>Fnv</code>和 <code>Murmur</code> 这两个简单的哈希函数。</p>
</blockquote>
<p>对于一个布隆过滤器，通常有如下定义：</p>
<ol>
<li>n 个 key。</li>
<li>m bits 的空间 v，全部初始化为0。</li>
</ol>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205031233283.png" alt=""></p>
<ol start="3">
<li><p>Bloom Filter 理论建议使用k个相互独立的哈希函数（Hash Function），用于表示<code>S={x1, x2,…,xn}</code>的n个元素的集合，对任意一个元素x，第 i 个哈希函数映射的位置hi(x) 就会被置为1（1≤i≤k）。</p>
<p> 如果有多个哈希函数位置都为1，那么只有 <strong>第一个哈希结果被使用</strong>。比如下面的图中从左往右数第二个“1”所在的位置就是最终哈希函数选中位置。</p>
</li>
</ol>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205031235855.png" alt=""></p>
<ol start="4">
<li><p>为了判断当前的元素是否在集合当中，需要对于当前的元素y进行k次的哈希函数，如果所有的hi(y)次数是1（i &lt;= i &lt;= k中的次数都是1）就认为当前的元素y<strong>可能</strong>在集合中，否则就绝对不存在。</p>
<p> 以下面的内容y1因为存在hash为0的结果，所以认为不存在于集合，而y2所有的hash都落在1上，可以认为<strong>可能</strong>存在集合。</p>
</li>
</ol>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205031927973.png" alt=""></p>
<p>布隆过滤器的理论内容相对简单，关键部分是哈希函数的选择和错误率的平衡。</p>
<p><strong>错误率计算</strong></p>
<p>首先布隆过滤器需要注意bit位长度，也就是数组长度。通常一个大的布隆过滤器会比小的布隆过滤器有更小的错误率。</p>
<p>误判率的计算公式为：<code>(1-e^(-kn/m))^k</code>。</p>
<p>推导过程如下，过程不是特别重要，了解最终公式即可：</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205032059650.png" alt=""></p>
<blockquote>
<p>n为key的个数，m为bits的位数（也就是数组大小）</p>
</blockquote>
<p>根据这个公式可以发现，需要先确定可能插入的数据集的容量大小 <em>n</em>, 然后再调整 k 和 <em>m</em> 来为你的应用配置过滤器，m 越大，k 越大， n 越小，那么误判率越小。</p>
<p>考虑到 p 为设置为0的概率，因此可以认为 m 有一半设置为1，一半设置为0时，误判率最低，注意这句话在最后的推导部分会详细介绍。</p>
<p><strong>多少个哈希函数？</strong></p>
<p>根据错误率计算结论，这里又有一个问题，就是究竟应该选择多少个哈希函数，哈希函数的过多容易导致计算效率降低影响性能，太少又会让误判率升高。</p>
<p>高兴的是，这个公式也有人推导出来了：</p>
<p><strong>hash 函数 k 的最优个数为 ln2 * (m/n)</strong>。</p>
<p>可以通过以下的步骤来确定 Bloom filter 的大小:</p>
<ol>
<li>确定 <em>n</em> 的变动范围</li>
<li>选定 <em>m</em> 的值</li>
<li>计算 <em>k</em> 的最优值</li>
<li>对于给定的n, <em>m</em>,  k计算错误率。如果这个错误率不能接受，那么回到第二步，否则结束</li>
</ol>
<p><strong>Bloom filter 的时间复杂度和空间复杂度?</strong></p>
<p>插入和测试操作的时间复杂度都是 O(k)，这是因为如果想要插入或者查询一个元素，只需要对于元素进行k次数的函数运算。</p>
<p>空间复杂度就比较难以估算了，因为误差率的存在，大小是难以确定的，如果难以估算一个过滤器的大小，最好选择一个哈希表或者一个可拓展的 Bloom filter。</p>
<blockquote>
<p>注意⚠️：LevelDB的过滤器大小是不能少于64位的bit数组。</p>
</blockquote>
<p><strong>m中多少位数为1合适</strong></p>
<p>直接记住结论：<strong>可以认为 m 有一半设置为1，一半设置为0时，误判率最低</strong>。</p>
<h1 id="levelDB实现"><a href="#levelDB实现" class="headerlink" title="levelDB实现"></a>levelDB实现</h1><p>LevelDB的布隆过滤器精髓在哈希函数上，它通过一个哈希达到多个哈希的性能，同时保证误判率在一定的限制。</p>
<p>具体的代码实现可以阅读<strong>bloom.cc</strong>：<span class="exturl" data-url="aHR0cHM6Ly9naXRodWIuY29tL2dvb2dsZS9sZXZlbGRiL2Jsb2IvbWFpbi91dGlsL2Jsb29tX3Rlc3QuY2M=" title="https://github.com/google/leveldb/blob/main/util/bloom_test.cc">leveldb/bloom_test.cc at main · google/leveldb · GitHub<i class="fa fa-external-link"></i></span></p>
<h2 id="index-md介绍"><a href="#index-md介绍" class="headerlink" title="index.md介绍"></a>index.md介绍</h2><p>这里先不深入源代码，先看看作者在<code>index.md</code>是如何解释的：<br><span class="exturl" data-url="aHR0cHM6Ly9naXRodWIuY29tL2dvb2dsZS9sZXZlbGRiL2Jsb2IvbWFpbi9kb2MvaW5kZXgubWQjZmlsdGVycw==" title="https://github.com/google/leveldb/blob/main/doc/index.md#filters">leveldb/index.md at main · google/leveldb · GitHub<i class="fa fa-external-link"></i></span></p>
<p>由于leveldb数据在磁盘上的组织方式，一个<code>Get()</code>的调用可能涉及到从磁盘上多次读取，所以可选的<code>FilterPolicy</code>机制可以被用来可以用来大大减少磁盘读取的次数，其实这里就是指的使用布隆过滤器提高过滤效率。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">leveldb::Options options;</span><br><span class="line"></span><br><span class="line">options.filter_policy = NewBloomFilterPolicy(<span class="number">10</span>);</span><br><span class="line"></span><br><span class="line">leveldb::DB* db;</span><br><span class="line"></span><br><span class="line">leveldb::DB::Open(options, <span class="string">"/tmp/testdb"</span>, &amp;db);</span><br><span class="line"></span><br><span class="line">... use the database ...</span><br><span class="line"></span><br><span class="line"><span class="keyword">delete</span> db;</span><br><span class="line"><span class="comment">// 注意，关闭leveldb的时候需要手动释放过滤器所占用内存空间</span></span><br><span class="line"><span class="keyword">delete</span> options.filter_policy;</span><br></pre></td></tr></table></figure>

<p>前面的代码将基于布隆过滤器的过滤策略与数据库联系起来。 </p>
<p>基于布隆过滤器的过滤依赖于在内存中为每个密钥保留一定数量的数据（本例中每个密钥为10bits，因为这是我们传递给<code>NewBloomFilterPolicy</code>的参数）。</p>
<p>这个过滤器将减少<code>Get()</code>调用所需的不必要的磁盘IO次数，提升效率大约是<strong>100倍</strong>。增加每一个key的位数将导致更大的减少，但<strong>代价占用是更多的内存</strong>。我们建议那些工作集不适合放在内存中的应用程序不适合在内存中使用，并且进行大量随机读取的应用程序设置一个过滤策略。</p>
<h2 id="FilterPolicy"><a href="#FilterPolicy" class="headerlink" title="FilterPolicy"></a>FilterPolicy</h2><p>整个过滤器通过对外的接口<code>FilterPolicy</code>，目的是减少<code>DB::Get()</code>函数调用时间，通常内部默认使用布隆过滤器。</p>
<p>下面是接口定义的代码：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">namespace</span> leveldb &#123;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Slice</span>;</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">LEVELDB_EXPORT</span> <span class="title">FilterPolicy</span> &#123;</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line"></span><br><span class="line"><span class="keyword">virtual</span> ~FilterPolicy();</span><br><span class="line"></span><br><span class="line"><span class="comment">// Return the name of this policy. Note that if the filter encoding</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// changes in an incompatible way, the name returned by this method</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// must be changed. Otherwise, old incompatible filters may be</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// passed to methods of this type.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/*返回该策略的名称。注意如果过滤器的编码变化，此方法返回的名称必须被改变。否则不兼容旧的过滤器可能被传递给这种类型的方法。</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="keyword">virtual</span> <span class="keyword">const</span> <span class="keyword">char</span>* <span class="title">Name</span><span class="params">()</span> <span class="keyword">const</span> </span>= <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="comment">// keys[0,n-1] contains a list of keys (potentially with duplicates)</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// that are ordered according to the user supplied comparator.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// Append a filter that summarizes keys[0,n-1] to *dst.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// Warning: do not change the initial contents of *dst. Instead,</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// append the newly constructed filter to *dst.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/* keys[0,n-1] 包含一个键的列表（可能有重复的）。根据用户提供的比较器进行排序。将一个总结keys[0,n-1]的过滤器追加到*dst。</span></span><br><span class="line"><span class="comment"> </span></span><br><span class="line"><span class="comment"> 警告：不要改变*dst的初始内容。 相反将新构建的过滤器追加到*dst中。</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="keyword">virtual</span> <span class="keyword">void</span> <span class="title">CreateFilter</span><span class="params">(<span class="keyword">const</span> Slice* keys, <span class="keyword">int</span> n,</span></span></span><br><span class="line"><span class="function"><span class="params"></span></span></span><br><span class="line"><span class="function"><span class="params"><span class="built_in">std</span>::<span class="built_in">string</span>* dst)</span> <span class="keyword">const</span> </span>= <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="comment">// "filter" contains the data appended by a preceding call to</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// CreateFilter() on this class. This method must return true if</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// the key was in the list of keys passed to CreateFilter().</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// This method may return true or false if the key was not on the</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// list, but it should aim to return false with a high probability.</span></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> "filter "包含了前面对这个类的CreateFilter()的调用所附加的数据。如果键在传递给CreateFilter()的键列表中，该方法必须返回true。如果键不在列表中，该方法可能会返回true或false，但它应该以返回false的概率大为目标。</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="keyword">virtual</span> <span class="keyword">bool</span> <span class="title">KeyMayMatch</span><span class="params">(<span class="keyword">const</span> Slice&amp; key, <span class="keyword">const</span> Slice&amp; filter)</span> <span class="keyword">const</span> </span>= <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 这一部分注释较多，放到后文介绍</span></span><br><span class="line"></span><br><span class="line"><span class="function">LEVELDB_EXPORT <span class="keyword">const</span> FilterPolicy* <span class="title">NewBloomFilterPolicy</span><span class="params">(<span class="keyword">int</span> bits_per_key)</span></span>;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">&#125; <span class="comment">// namespace leveldb</span></span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">endif</span> <span class="comment">// STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_</span></span></span><br></pre></td></tr></table></figure>

<h2 id="bloom-cc"><a href="#bloom-cc" class="headerlink" title="bloom.cc"></a>bloom.cc</h2><p>关于具体的代码解释放在了注释当中，比较值得关注的是创建过滤器的部分以及哈希函数的部分，这部分介绍的是过滤器本身的源代码，关键的哈希函数放到了下面的小节。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// Copyright (c) 2012 The LevelDB Authors. All rights reserved.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// Use of this source code is governed by a BSD-style license that can be</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// found in the LICENSE file. See the AUTHORS file for names of contributors.</span></span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"leveldb/filter_policy.h"</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"leveldb/Slice.h"</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"util/hash.h"</span></span></span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="keyword">namespace</span> leveldb &#123;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="keyword">namespace</span> &#123;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 哈希函数</span></span><br><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">uint32_t</span> <span class="title">BloomHash</span><span class="params">(<span class="keyword">const</span> Slice&amp; key)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 注意 0xbc9f1d34</span></span><br><span class="line">	<span class="keyword">return</span> Hash(key.data(), key.size(), <span class="number">0xbc9f1d34</span>);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">BloomFilterPolicy</span> :</span> <span class="keyword">public</span> FilterPolicy &#123;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="function"><span class="keyword">explicit</span> <span class="title">BloomFilterPolicy</span><span class="params">(<span class="keyword">int</span> bits_per_key)</span> : <span class="title">bits_per_key_</span><span class="params">(bits_per_key)</span> </span>&#123;</span><br><span class="line">	</span><br><span class="line">		<span class="comment">// We intentionally round down to reduce probing cost a little bit</span></span><br><span class="line">		<span class="comment">// 我们有意四舍五入，以减少一点探测成本</span></span><br><span class="line">		k_ = <span class="keyword">static_cast</span>&lt;<span class="keyword">size_t</span>&gt;(bits_per_key * <span class="number">0.69</span>); <span class="comment">// 0.69 =~ ln(2)</span></span><br><span class="line">	</span><br><span class="line">		<span class="keyword">if</span> (k_ &lt; <span class="number">1</span>) k_ = <span class="number">1</span>;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">if</span> (k_ &gt; <span class="number">30</span>) k_ = <span class="number">30</span>;</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">const</span> <span class="keyword">char</span>* <span class="title">Name</span><span class="params">()</span> <span class="keyword">const</span> <span class="keyword">override</span> </span>&#123; <span class="keyword">return</span> <span class="string">"leveldb.BuiltinBloomFilter2"</span>; &#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">CreateFilter</span><span class="params">(<span class="keyword">const</span> Slice* keys, <span class="keyword">int</span> n, <span class="built_in">std</span>::<span class="built_in">string</span>* dst)</span> <span class="keyword">const</span> <span class="keyword">override</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// Compute bloom filter size (in both bits and bytes)</span></span><br><span class="line">	<span class="comment">// 计算布过滤器的大小（包括比特和字节）。</span></span><br><span class="line">	<span class="keyword">size_t</span> bits = n * bits_per_key_;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">	<span class="comment">// For small n, we can see a very high false positive rate. Fix it</span></span><br><span class="line">	</span><br><span class="line">	<span class="comment">// by enforcing a minimum bloom filter length.</span></span><br><span class="line">	<span class="comment">// 对于小的n，我们可以看到一个非常高的误判率。通过强制执行最小Bloom filter长度来解决这个问题。</span></span><br><span class="line">	<span class="comment">// tip: 这里就是之前说的如果bit位数过小会增加误判率</span></span><br><span class="line">	<span class="keyword">if</span> (bits &lt; <span class="number">64</span>) bits = <span class="number">64</span>;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">size_t</span> bytes = (bits + <span class="number">7</span>) / <span class="number">8</span>;</span><br><span class="line">	<span class="comment">// 至少有64个bits</span></span><br><span class="line">	bits = bytes * <span class="number">8</span>;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">const</span> <span class="keyword">size_t</span> init_size = dst-&gt;size();</span><br><span class="line">	<span class="comment">// 调整容器的大小，使其包含_n个_元素。</span></span><br><span class="line">	dst-&gt;resize(init_size + bytes, <span class="number">0</span>);</span><br><span class="line">	</span><br><span class="line">	dst-&gt;push_back(<span class="keyword">static_cast</span>&lt;<span class="keyword">char</span>&gt;(k_)); <span class="comment">// Remember # of probes in filter</span></span><br><span class="line">	</span><br><span class="line">	<span class="keyword">char</span>* <span class="built_in">array</span> = &amp;(*dst)[init_size];</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">	</span><br><span class="line">		<span class="comment">// Use double-hashing to generate a sequence of hash values.</span></span><br><span class="line">		<span class="comment">// See analysis in [Kirsch,Mitzenmacher 2006].</span></span><br><span class="line">		<span class="comment">// 使用双重哈希法生成一连串的哈希值。见[Kirsch,Mitzenmacher 2006]中的分析。</span></span><br><span class="line">		<span class="comment">// tips: 原始论文请看参考资料 -&gt; LNCS 4168 - Less Hashing, Same Performance: Building a Better Bloom Filter (harvard.edu)</span></span><br><span class="line">		<span class="keyword">uint32_t</span> h = BloomHash(keys[i]);</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">const</span> <span class="keyword">uint32_t</span> delta = (h &gt;&gt; <span class="number">17</span>) | (h &lt;&lt; <span class="number">15</span>); <span class="comment">// // 向右旋转17位</span></span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">size_t</span> j = <span class="number">0</span>; j &lt; k_; j++) &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">const</span> <span class="keyword">uint32_t</span> bitpos = h % bits;</span><br><span class="line">		</span><br><span class="line">		<span class="built_in">array</span>[bitpos / <span class="number">8</span>] |= (<span class="number">1</span> &lt;&lt; (bitpos % <span class="number">8</span>));</span><br><span class="line">		</span><br><span class="line">		h += delta;</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line">	<span class="comment">/*</span></span><br><span class="line"><span class="comment">		关键函数：</span></span><br><span class="line"><span class="comment">		</span></span><br><span class="line"><span class="comment">	*/</span></span><br><span class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">KeyMayMatch</span><span class="params">(<span class="keyword">const</span> Slice&amp; key, <span class="keyword">const</span> Slice&amp; bloom_filter)</span> <span class="keyword">const</span> <span class="keyword">override</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">const</span> <span class="keyword">size_t</span> len = bloom_filter.size();</span><br><span class="line">	</span><br><span class="line">	<span class="comment">// 只有1位的过滤器无意义</span></span><br><span class="line">	<span class="keyword">if</span> (len &lt; <span class="number">2</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">const</span> <span class="keyword">char</span>* <span class="built_in">array</span> = bloom_filter.data();</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">const</span> <span class="keyword">size_t</span> bits = (len - <span class="number">1</span>) * <span class="number">8</span>;  </span><br><span class="line"></span><br><span class="line">	<span class="comment">// Use the encoded k so that we can read filters generated by</span></span><br><span class="line">	<span class="comment">// bloom filters created using different parameters.</span></span><br><span class="line">	</span><br><span class="line">	<span class="comment">// 使用编码的k，这样我们就可以读取由 使用不同参数创建的bloom过滤器。</span></span><br><span class="line">	<span class="keyword">const</span> <span class="keyword">size_t</span> k = <span class="built_in">array</span>[len - <span class="number">1</span>];</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (k &gt; <span class="number">30</span>) &#123;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 超过我们设定 k 个数，直接返回 true，不滤掉该 SSTable.</span></span><br><span class="line"></span><br><span class="line">		<span class="comment">// Reserved for potentially new encodings for short bloom filters.</span></span><br><span class="line">		<span class="comment">// Consider it a match.</span></span><br><span class="line">		<span class="comment">// 保留给可能出现的新编码的短Bloom过滤器。认为它是一种匹配。</span></span><br><span class="line">		<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 关键：哈希函数</span></span><br><span class="line">	<span class="keyword">uint32_t</span> h = BloomHash(key);</span><br><span class="line">	<span class="comment">// 右旋17位</span></span><br><span class="line">	<span class="keyword">const</span> <span class="keyword">uint32_t</span> delta = (h &gt;&gt; <span class="number">17</span>) | (h &lt;&lt; <span class="number">15</span>); <span class="comment">// Rotate right 17 bits</span></span><br><span class="line">	</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">size_t</span> j = <span class="number">0</span>; j &lt; k; j++) &#123;</span><br><span class="line">	</span><br><span class="line">		<span class="keyword">const</span> <span class="keyword">uint32_t</span> bitpos = h % bits;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">if</span> ((<span class="built_in">array</span>[bitpos / <span class="number">8</span>] &amp; (<span class="number">1</span> &lt;&lt; (bitpos % <span class="number">8</span>))) == <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">		</span><br><span class="line">			h += delta;</span><br><span class="line">		</span><br><span class="line">		&#125;</span><br><span class="line">	</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">	<span class="keyword">private</span>:</span><br><span class="line">	</span><br><span class="line">		<span class="keyword">size_t</span> bits_per_key_;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">size_t</span> k_;</span><br><span class="line">		</span><br><span class="line">		&#125;;</span><br><span class="line">	</span><br><span class="line">	&#125; <span class="comment">// namespace</span></span><br><span class="line"></span><br><span class="line">  </span><br><span class="line">	<span class="comment">// 新的布隆过滤器策略（请看下文注释）</span></span><br><span class="line">	<span class="function"><span class="keyword">const</span> FilterPolicy* <span class="title">NewBloomFilterPolicy</span><span class="params">(<span class="keyword">int</span> bits_per_key)</span> </span>&#123;</span><br><span class="line">	</span><br><span class="line">		<span class="keyword">return</span> <span class="keyword">new</span> BloomFilterPolicy(bits_per_key);</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">&#125; <span class="comment">// namespace leveldb</span></span><br></pre></td></tr></table></figure>

<p><strong>NewBloomFilterPolicy</strong>函数</p>
<p>为什么叫做新的布隆过滤器策略，可以看作者所给的注释：</p>
<blockquote>
<p>返回一个新的过滤策略，该策略使用一个Bloom过滤器，每个密钥大约有指定的每个密钥的比特数。键的比特数是10。<br>最终测试最佳值是10，这将产生一个误报率为1%的过滤器。</p>
</blockquote>
<p>注意使用之后必须要<strong>手动</strong>释放掉相关对象内存：</p>
<blockquote>
<p>调用者必须在使用该结果的<strong>任何数据库关闭后删除该结果</strong>，数据库被关闭后，调用者必须删除该结果。</p>
</blockquote>
<p>如果使用的是自定义的比较器，它忽略了被比较的键的某些部分以及被比较的键的某些部分，这时候不允许使用<code>NewBloomFilterPolicy()</code>，而必须提供自定义的<code>FilterPolicy</code>实现，因为原始的过滤器它也忽略了键的相应部分。</p>
<p>例如，如果<strong>比较器忽略了尾部的空格</strong>，那么使用一个的<code>FilterPolicy</code>（比如<code>NewBloomFilterPolicy</code>），原始对<code>FilterPolicy（如NewBloomFilterPolicy）</code>行为就会出现失误，因为它<strong>不会忽略键的尾部空格</strong>。</p>
<h2 id="hash-cc"><a href="#hash-cc" class="headerlink" title="hash.cc"></a>hash.cc</h2><p>之前说过关键的代码其中之一是优质的哈希函数，下面是<code>hash.cc</code>的相关代码：</p>
<p>注意这里的哈希函数使用的伪随机数种子为<code>0xbc9f1d34</code>，对应的10进制为<code>9134</code>。</p>
<p>这里也可以看到LevelDB利用自己的优质哈希函数，使得一个函数取代N个函数的效果，这算是对理论的调整，内部也控制levelDB长度最少为64个bit位。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">data：bit 位数</span></span><br><span class="line"><span class="comment">n：n 个 key</span></span><br><span class="line"><span class="comment">seed：种子，实际固定为 0xbc9f1d34</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="keyword">uint32_t</span> <span class="title">Hash</span><span class="params">(<span class="keyword">const</span> <span class="keyword">char</span>* data, <span class="keyword">size_t</span> n, <span class="keyword">uint32_t</span> seed)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// Similar to murmur hash</span></span><br><span class="line">	<span class="comment">// 类似杂音哈希</span></span><br><span class="line">	<span class="keyword">const</span> <span class="keyword">uint32_t</span> m = <span class="number">0xc6a4a793</span>;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">const</span> <span class="keyword">uint32_t</span> r = <span class="number">24</span>;</span><br><span class="line">	<span class="comment">// limit指向了char*数组的最后一个位置的下一个位置，类似于迭代器end()</span></span><br><span class="line">	<span class="keyword">const</span> <span class="keyword">char</span>* limit = data + n;</span><br><span class="line">	  </span><br><span class="line">	<span class="keyword">uint32_t</span> h = seed ^ (n * m);</span><br><span class="line">	</span><br><span class="line">	<span class="comment">// Pick up four bytes at a time</span></span><br><span class="line">	<span class="comment">// 以4个字节作为一次解析	</span></span><br><span class="line">	<span class="keyword">while</span> (data + <span class="number">4</span> &lt;= limit) &#123;</span><br><span class="line">		<span class="comment">//  每次解码前4个字节，直到最后剩下小于4个字节</span></span><br><span class="line"></span><br><span class="line">		<span class="comment">// DecodeFixed32 低级别的Get...版本，直接从字符缓冲区读取 而不进行任何边界检查，最近的clang和gcc将其优化为一条 mov / ldr 指令。</span></span><br><span class="line">		<span class="keyword">uint32_t</span> w = DecodeFixed32(data);</span><br><span class="line">		</span><br><span class="line">		data += <span class="number">4</span>;</span><br><span class="line">		</span><br><span class="line">		h += w;</span><br><span class="line">		</span><br><span class="line">		h *= m;</span><br><span class="line">		</span><br><span class="line">		h ^= (h &gt;&gt; <span class="number">16</span>);</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">// Pick up remaining bytes</span></span><br><span class="line">	<span class="comment">// 处理剩余的字节	</span></span><br><span class="line">	<span class="keyword">switch</span> (limit - data) &#123;</span><br><span class="line">		<span class="comment">// 将剩下的字节转化到uint32_t里面</span></span><br><span class="line">		<span class="keyword">case</span> <span class="number">3</span>:</span><br><span class="line">			<span class="comment">// static_cast 表示的是良性转换，含义表示</span></span><br><span class="line">			h += <span class="keyword">static_cast</span>&lt;<span class="keyword">uint8_t</span>&gt;(data[<span class="number">2</span>]) &lt;&lt; <span class="number">16</span>;</span><br><span class="line">			</span><br><span class="line">			<span class="comment">// FALLTHROUGH_INTENDED宏可以用来注解开关标签之间的隐性落差。真正的定义应该由外部提供。 这个是为不支持的编译器提供的后备版本。</span></span><br><span class="line">			<span class="comment">/*</span></span><br><span class="line"><span class="comment">			#ifndef FALLTHROUGH_INTENDED</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">			#define FALLTHROUGH_INTENDED \</span></span><br><span class="line"><span class="comment">			</span></span><br><span class="line"><span class="comment">			do &#123; \</span></span><br><span class="line"><span class="comment">			</span></span><br><span class="line"><span class="comment">			&#125; while (0)</span></span><br><span class="line"><span class="comment">			</span></span><br><span class="line"><span class="comment">			#endif</span></span><br><span class="line"><span class="comment">			*/</span></span><br><span class="line">			FALLTHROUGH_INTENDED;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">case</span> <span class="number">2</span>:</span><br><span class="line">		</span><br><span class="line">			h += <span class="keyword">static_cast</span>&lt;<span class="keyword">uint8_t</span>&gt;(data[<span class="number">1</span>]) &lt;&lt; <span class="number">8</span>;</span><br><span class="line">			</span><br><span class="line">			FALLTHROUGH_INTENDED;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">case</span> <span class="number">1</span>:</span><br><span class="line">		</span><br><span class="line">			h += <span class="keyword">static_cast</span>&lt;<span class="keyword">uint8_t</span>&gt;(data[<span class="number">0</span>]);</span><br><span class="line">			</span><br><span class="line">			h *= m;</span><br><span class="line">			</span><br><span class="line">			h ^= (h &gt;&gt; r);</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">break</span>;</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">return</span> h;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="Slice-h"><a href="#Slice-h" class="headerlink" title="Slice.h"></a>Slice.h</h2><p>可以看作类似Redis的简单字符串sds设计，只不过语言使用的是c++。</p>
<p>相关解释可以阅读文档：</p>
<p><span class="exturl" data-url="aHR0cHM6Ly9naXRodWIuY29tL2dvb2dsZS9sZXZlbGRiL2Jsb2IvbWFpbi9kb2MvaW5kZXgubWQjU2xpY2U=" title="https://github.com/google/leveldb/blob/main/doc/index.md#Slice">leveldb/index.md at main · google/leveldb · GitHub<i class="fa fa-external-link"></i></span></p>
<p>Slice 是一个简单的数据结构，包含一个进入一些外部存储的指针和size。 Slice的用户必须确保在相应的外部存储被取消分配后不使用该Slice（用完必须手动释放内存）。</p>
<p>多个线程可以在一个Slice上调用<strong>const方法</strong>而不需要外部同步（线程安全对象），但如果任何一个线程可能会调用非const方法，所有访问同一Slice的线程都必须使用外部同步。</p>
<p>C++ 或者类C的 字符串可以简单的转化为Slice：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">leveldb::Slice s1 = <span class="string">"hello"</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="built_in">std</span>::<span class="built_in">string</span> <span class="title">str</span><span class="params">(<span class="string">"world"</span>)</span></span>;</span><br><span class="line">leveldb::Slice s2 = str;</span><br></pre></td></tr></table></figure>

<p>反过来也是一样的：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">std</span>::<span class="built_in">string</span> str = s1.ToString();</span><br><span class="line">assert(str == <span class="built_in">std</span>::<span class="built_in">string</span>(<span class="string">"hello"</span>));</span><br></pre></td></tr></table></figure>

<p>在使用Slice时要小心因为要由调用者来确保Slice所指向的外部字节数组在Slice使用时保持有效。例如，下面的例子是错误的：</p>
<p>下面的例子中Slice将可能指向一个外部的引用，同时不保证外部引用存在。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">leveldb::Slice Slice;</span><br><span class="line"><span class="keyword">if</span> (...) &#123;</span><br><span class="line">  <span class="built_in">std</span>::<span class="built_in">string</span> str = ...;</span><br><span class="line">  Slice = str;</span><br><span class="line">&#125;</span><br><span class="line">Use(Slice);</span><br></pre></td></tr></table></figure>

<p>当if语句超出范围时，str将被销毁，Slice的存储内容将消失。</p>
<h1 id="其他内容"><a href="#其他内容" class="headerlink" title="其他内容"></a>其他内容</h1><h2 id="单元测试"><a href="#单元测试" class="headerlink" title="单元测试"></a>单元测试</h2><p>作者编写的单元测试可以更为直观的看到具体效果，路径为：<code>/leveldb-main/util/bloom_test.cc</code>。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br><span class="line">245</span><br><span class="line">246</span><br><span class="line">247</span><br><span class="line">248</span><br><span class="line">249</span><br><span class="line">250</span><br><span class="line">251</span><br><span class="line">252</span><br><span class="line">253</span><br><span class="line">254</span><br><span class="line">255</span><br><span class="line">256</span><br><span class="line">257</span><br><span class="line">258</span><br><span class="line">259</span><br><span class="line">260</span><br><span class="line">261</span><br><span class="line">262</span><br><span class="line">263</span><br><span class="line">264</span><br><span class="line">265</span><br><span class="line">266</span><br><span class="line">267</span><br><span class="line">268</span><br><span class="line">269</span><br><span class="line">270</span><br><span class="line">271</span><br><span class="line">272</span><br><span class="line">273</span><br><span class="line">274</span><br><span class="line">275</span><br><span class="line">276</span><br><span class="line">277</span><br><span class="line">278</span><br><span class="line">279</span><br><span class="line">280</span><br><span class="line">281</span><br><span class="line">282</span><br><span class="line">283</span><br><span class="line">284</span><br><span class="line">285</span><br><span class="line">286</span><br><span class="line">287</span><br><span class="line">288</span><br><span class="line">289</span><br><span class="line">290</span><br><span class="line">291</span><br><span class="line">292</span><br><span class="line">293</span><br><span class="line">294</span><br><span class="line">295</span><br><span class="line">296</span><br><span class="line">297</span><br><span class="line">298</span><br><span class="line">299</span><br><span class="line">300</span><br><span class="line">301</span><br><span class="line">302</span><br><span class="line">303</span><br><span class="line">304</span><br><span class="line">305</span><br><span class="line">306</span><br><span class="line">307</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// Copyright (c) 2012 The LevelDB Authors. All rights reserved.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// Use of this source code is governed by a BSD-style license that can be</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// found in the LICENSE file. See the AUTHORS file for names of contributors.</span></span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"gtest/gtest.h"</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"leveldb/filter_policy.h"</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"util/coding.h"</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"util/logging.h"</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"util/testutil.h"</span></span></span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="keyword">namespace</span> leveldb &#123;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">	<span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">int</span> kVerbose = <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">static</span> Slice <span class="title">Key</span><span class="params">(<span class="keyword">int</span> i, <span class="keyword">char</span>* buffer)</span> </span>&#123;</span><br><span class="line">	</span><br><span class="line">	EncodeFixed32(buffer, i);</span><br><span class="line">	</span><br><span class="line">		<span class="keyword">return</span> Slice(buffer, <span class="keyword">sizeof</span>(<span class="keyword">uint32_t</span>));</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">BloomTest</span> :</span> <span class="keyword">public</span> testing::Test &#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">public</span>:</span><br><span class="line">	</span><br><span class="line">	BloomTest() : policy_(NewBloomFilterPolicy(<span class="number">10</span>)) &#123;&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">	~BloomTest() &#123; <span class="keyword">delete</span> policy_; &#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">Reset</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		</span><br><span class="line">		keys_.clear();</span><br><span class="line">		</span><br><span class="line">		filter_.clear();</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">Add</span><span class="params">(<span class="keyword">const</span> Slice&amp; s)</span> </span>&#123; keys_.push_back(s.ToString()); &#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line">	<span class="comment">// </span></span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">Build</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	</span><br><span class="line">		<span class="built_in">std</span>::<span class="built_in">vector</span>&lt;Slice&gt; key_Slices;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">size_t</span> i = <span class="number">0</span>; i &lt; keys_.size(); i++) &#123;</span><br><span class="line">		</span><br><span class="line">			key_Slices.push_back(Slice(keys_[i]));</span><br><span class="line">		</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		filter_.clear();</span><br><span class="line">		</span><br><span class="line">		policy_-&gt;CreateFilter(&amp;key_Slices[<span class="number">0</span>], <span class="keyword">static_cast</span>&lt;<span class="keyword">int</span>&gt;(key_Slices.size()),</span><br><span class="line">		</span><br><span class="line">		&amp;filter_);</span><br><span class="line">		</span><br><span class="line">		keys_.clear();</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">if</span> (kVerbose &gt;= <span class="number">2</span>) DumpFilter();</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">size_t</span> <span class="title">FilterSize</span><span class="params">()</span> <span class="keyword">const</span> </span>&#123; <span class="keyword">return</span> filter_.size(); &#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line">	<span class="comment">// 打印</span></span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">DumpFilter</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	</span><br><span class="line">		<span class="built_in">std</span>::<span class="built_in">fprintf</span>(<span class="built_in">stderr</span>, <span class="string">"F("</span>);</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">size_t</span> i = <span class="number">0</span>; i + <span class="number">1</span> &lt; filter_.size(); i++) &#123;</span><br><span class="line">		</span><br><span class="line">			<span class="keyword">const</span> <span class="keyword">unsigned</span> <span class="keyword">int</span> c = <span class="keyword">static_cast</span>&lt;<span class="keyword">unsigned</span> <span class="keyword">int</span>&gt;(filter_[i]);</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; <span class="number">8</span>; j++) &#123;</span><br><span class="line">			</span><br><span class="line">			<span class="built_in">std</span>::<span class="built_in">fprintf</span>(<span class="built_in">stderr</span>, <span class="string">"%c"</span>, (c &amp; (<span class="number">1</span> &lt;&lt; j)) ? <span class="string">'1'</span> : <span class="string">'.'</span>);</span><br><span class="line">		</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		&#125;</span><br><span class="line">	</span><br><span class="line">		<span class="built_in">std</span>::<span class="built_in">fprintf</span>(<span class="built_in">stderr</span>, <span class="string">")\n"</span>);</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line">	<span class="comment">// 匹配</span></span><br><span class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">Matches</span><span class="params">(<span class="keyword">const</span> Slice&amp; s)</span> </span>&#123;</span><br><span class="line">	</span><br><span class="line">		<span class="keyword">if</span> (!keys_.empty()) &#123;</span><br><span class="line">		</span><br><span class="line">			Build();</span><br><span class="line">		</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">return</span> policy_-&gt;KeyMayMatch(s, filter_);</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line">	</span><br><span class="line">	<span class="function"><span class="keyword">double</span> <span class="title">FalsePositiveRate</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	</span><br><span class="line">		<span class="keyword">char</span> buffer[<span class="keyword">sizeof</span>(<span class="keyword">int</span>)];</span><br><span class="line">		</span><br><span class="line">			<span class="keyword">int</span> result = <span class="number">0</span>;</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">10000</span>; i++) &#123;</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">if</span> (Matches(Key(i + <span class="number">1000000000</span>, buffer))) &#123;</span><br><span class="line">			</span><br><span class="line">			result++;</span><br><span class="line">		</span><br><span class="line">		&#125;</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">return</span> result / <span class="number">10000.0</span>;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line"></span><br><span class="line">	<span class="keyword">const</span> FilterPolicy* policy_;</span><br><span class="line">	</span><br><span class="line">	<span class="built_in">std</span>::<span class="built_in">string</span> filter_;</span><br><span class="line">	</span><br><span class="line">	<span class="built_in">std</span>::<span class="built_in">vector</span>&lt;<span class="built_in">std</span>::<span class="built_in">string</span>&gt; keys_;</span><br><span class="line"></span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">TEST_F(BloomTest, EmptyFilter) &#123;</span><br><span class="line">	</span><br><span class="line">	ASSERT_TRUE(!Matches(<span class="string">"hello"</span>));</span><br><span class="line">	</span><br><span class="line">	ASSERT_TRUE(!Matches(<span class="string">"world"</span>));</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">TEST_F(BloomTest, Small) &#123;</span><br><span class="line">	</span><br><span class="line">	Add(<span class="string">"hello"</span>);</span><br><span class="line">	</span><br><span class="line">	Add(<span class="string">"world"</span>);</span><br><span class="line">	</span><br><span class="line">	ASSERT_TRUE(Matches(<span class="string">"hello"</span>));</span><br><span class="line">	</span><br><span class="line">	ASSERT_TRUE(Matches(<span class="string">"world"</span>));</span><br><span class="line">	</span><br><span class="line">	ASSERT_TRUE(!Matches(<span class="string">"x"</span>));</span><br><span class="line">	</span><br><span class="line">	ASSERT_TRUE(!Matches(<span class="string">"foo"</span>));</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">int</span> <span class="title">NextLength</span><span class="params">(<span class="keyword">int</span> length)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (length &lt; <span class="number">10</span>) &#123;</span><br><span class="line">	</span><br><span class="line">		length += <span class="number">1</span>;</span><br><span class="line">	</span><br><span class="line">	&#125; <span class="keyword">else</span> <span class="keyword">if</span> (length &lt; <span class="number">100</span>) &#123;</span><br><span class="line">	</span><br><span class="line">		length += <span class="number">10</span>;</span><br><span class="line">	</span><br><span class="line">	&#125; <span class="keyword">else</span> <span class="keyword">if</span> (length &lt; <span class="number">1000</span>) &#123;</span><br><span class="line">	</span><br><span class="line">		length += <span class="number">100</span>;</span><br><span class="line">	</span><br><span class="line">	&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">	</span><br><span class="line">		length += <span class="number">1000</span>;</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">return</span> length;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">TEST_F(BloomTest, VaryingLengths) &#123;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">char</span> buffer[<span class="keyword">sizeof</span>(<span class="keyword">int</span>)];</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line">	</span><br><span class="line">	<span class="comment">// Count number of filters that significantly exceed the false positive rate</span></span><br><span class="line">	</span><br><span class="line">	<span class="keyword">int</span> mediocre_filters = <span class="number">0</span>;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">int</span> good_filters = <span class="number">0</span>;</span><br><span class="line">	</span><br><span class="line">	  </span><br><span class="line">	</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> length = <span class="number">1</span>; length &lt;= <span class="number">10000</span>; length = NextLength(length)) &#123;</span><br><span class="line">	</span><br><span class="line">	Reset();</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; length; i++) &#123;</span><br><span class="line">	</span><br><span class="line">	Add(Key(i, buffer));</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">	Build();</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">ASSERT_LE(FilterSize(), <span class="keyword">static_cast</span>&lt;<span class="keyword">size_t</span>&gt;((length * <span class="number">10</span> / <span class="number">8</span>) + <span class="number">40</span>))</span><br><span class="line"></span><br><span class="line">&lt;&lt; length;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="comment">// All added keys must match</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; length; i++) &#123;</span><br><span class="line"></span><br><span class="line">	ASSERT_TRUE(Matches(Key(i, buffer)))</span><br><span class="line">	</span><br><span class="line">	&lt;&lt; <span class="string">"Length "</span> &lt;&lt; length &lt;&lt; <span class="string">"; key "</span> &lt;&lt; i;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="comment">// Check false positive rate</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">double</span> rate = FalsePositiveRate();</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (kVerbose &gt;= <span class="number">1</span>) &#123;</span><br><span class="line">	</span><br><span class="line">		<span class="built_in">std</span>::<span class="built_in">fprintf</span>(<span class="built_in">stderr</span>,</span><br><span class="line">		</span><br><span class="line">		<span class="string">"False positives: %5.2f%% @ length = %6d ; bytes = %6d\n"</span>,</span><br><span class="line">		</span><br><span class="line">		rate * <span class="number">100.0</span>, length, <span class="keyword">static_cast</span>&lt;<span class="keyword">int</span>&gt;(FilterSize()));</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	ASSERT_LE(rate, <span class="number">0.02</span>); <span class="comment">// Must not be over 2%</span></span><br><span class="line">	</span><br><span class="line">	<span class="keyword">if</span> (rate &gt; <span class="number">0.0125</span>)</span><br><span class="line">	</span><br><span class="line">		mediocre_filters++; <span class="comment">// Allowed, but not too often</span></span><br><span class="line">	</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	</span><br><span class="line">		good_filters++;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> (kVerbose &gt;= <span class="number">1</span>) &#123;</span><br><span class="line">	</span><br><span class="line">	<span class="built_in">std</span>::<span class="built_in">fprintf</span>(<span class="built_in">stderr</span>, <span class="string">"Filters: %d good, %d mediocre\n"</span>, good_filters,</span><br><span class="line">	</span><br><span class="line">	mediocre_filters);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">	ASSERT_LE(mediocre_filters, good_filters / <span class="number">5</span>);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line"><span class="comment">// Different bits-per-byte</span></span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">&#125; <span class="comment">// namespace leveldb</span></span><br></pre></td></tr></table></figure>
<h2 id="c-语法"><a href="#c-语法" class="headerlink" title="c++语法"></a>c++语法</h2><p>补充：<br>个人并没有学过C++，所以这部分补充一些不理解的关键字和语法含义。</p>
<p><strong>explicit</strong></p>
<p><span class="exturl" data-url="aHR0cHM6Ly9saW5rLnpoaWh1LmNvbS8/dGFyZ2V0PWh0dHBzJTNBLy96aC5jcHByZWZlcmVuY2UuY29tL3cvY3BwL2xhbmd1YWdlL2V4cGxpY2l0" title="https://link.zhihu.com/?target=https%3A//zh.cppreference.com/w/cpp/language/explicit">C++ 参考手册<i class="fa fa-external-link"></i></span>如下解释：</p>
<ul>
<li><code>explicit</code>修饰的构造函数不能被隐式调用。</li>
<li>禁止类对象之间的隐式转换。</li>
</ul>
<p>这篇文章我们关注的就是第一点：<strong>构造函数被<code>explicit</code>修饰后, 就不能再被隐式调用了</strong>。</p>
<p>这里用了网上相关的案例：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;string&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Explicit</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">private</span>:</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span>:</span><br><span class="line">        Explicit(<span class="keyword">int</span> <span class="built_in">size</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">std</span>::<span class="built_in">cout</span> &lt;&lt; <span class="string">" the size is "</span> &lt;&lt; <span class="built_in">size</span> &lt;&lt; <span class="built_in">std</span>::<span class="built_in">endl</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        Explicit(<span class="keyword">const</span> <span class="keyword">char</span>* str)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">std</span>::<span class="built_in">string</span> _str = str;</span><br><span class="line">            <span class="built_in">std</span>::<span class="built_in">cout</span> &lt;&lt; <span class="string">" the str is "</span> &lt;&lt; _str &lt;&lt; <span class="built_in">std</span>::<span class="built_in">endl</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        Explicit(<span class="keyword">const</span> Explicit&amp; ins)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">std</span>::<span class="built_in">cout</span> &lt;&lt; <span class="string">" The Explicit is ins"</span> &lt;&lt; <span class="built_in">std</span>::<span class="built_in">endl</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        Explicit(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">std</span>::<span class="built_in">cout</span> &lt;&lt; <span class="string">" the a is "</span> &lt;&lt; a  &lt;&lt; <span class="string">" the b is "</span> &lt;&lt; b &lt;&lt; <span class="built_in">std</span>::<span class="built_in">endl</span>;</span><br><span class="line">        &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="function">Explicit <span class="title">test0</span><span class="params">(<span class="number">15</span>)</span></span>;</span><br><span class="line">    Explicit test1 = <span class="number">10</span>;<span class="comment">// 隐式调用Explicit(int size)</span></span><br><span class="line"></span><br><span class="line">    <span class="function">Explicit <span class="title">test2</span><span class="params">(<span class="string">"RIGHTRIGHT"</span>)</span></span>;</span><br><span class="line">    Explicit test3 = <span class="string">"BUGBUGBUG"</span>;<span class="comment">// 隐式调用Explicit(const char* str)</span></span><br><span class="line"></span><br><span class="line">    <span class="function">Explicit <span class="title">test4</span><span class="params">(<span class="number">1</span>, <span class="number">10</span>)</span></span>;</span><br><span class="line">    Explicit test5 = test1;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>虽然程序没有错误，但是把一个<code>int</code>类型或者<code>const char*</code>类型的变量赋值给<code>Explicit</code>类型的变量看起来总归不是很好，并且一旦使用出错很难排查，所以这时候构造函数被<code>explicit</code>修饰后, 就不能再被隐式调用了，添加关键字之后的效果不演示了，加上之后整个程序是无法通过编译的。</p>
<p>吐槽：很神经病的东西，在过去的版本中使用隐式调用提高编码效率，结果后面发现坑太大挖坑自己填。</p>
<p><strong>resize函数</strong></p>
<p>直接看下面的案例更容易理解：</p>
<ul>
<li>myvector.resize(5);<br>将原来有10个数的vector数组，调整为5个数的长度，多余的数删掉，释放内存。 <strong>5 &lt; 10 减小数组长度</strong></li>
<li>myvector.resize(8,100);<br>将5个数长度的vector数组的长度调整为8，不够的数用100来填补，即增加了3个100。 <strong>8 &gt; 5 增大数组长度，指定填充元素</strong></li>
<li>myvector.resize(12);<br>将8个数长度的vector数组的长度调整为12，用0默认填补，即增加了4个0。 <strong>12 &gt; 8 增大数组长度，未指定填充元素</strong></li>
</ul>
<h2 id="数学推导"><a href="#数学推导" class="headerlink" title="数学推导"></a>数学推导</h2><p>推导部分给想要更加深入了解的人，可以直接记住上面的结论，看不懂也没关系。</p>
<p>下面的大部分内容来自论文根据 <span class="exturl" data-url="aHR0cDovL3d3dy5lZWNzLmhhcnZhcmQuZWR1L35taWNoYWVsbS9wb3N0c2NyaXB0cy9lc2EyMDA2YS5wZGY=" title="http://www.eecs.harvard.edu/~michaelm/postscripts/esa2006a.pdf">LNCS 4168 - Less Hashing, Same Performance: Building a Better Bloom Filter (harvard.edu)<i class="fa fa-external-link"></i></span> 翻译。</p>
<blockquote>
<p> <code>false position</code>：误判率，也就是随着哈希和为1的bit位增加导致的误判率上升。</p>
</blockquote>
<p>根据 bloom filter 的组成，对一个指定的 bit，其被设置为0、1的概率分别为：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">P(<span class="number">1</span>) = <span class="number">1</span>/m</span><br><span class="line">P(<span class="number">0</span>) = <span class="number">1</span> - <span class="number">1</span>/m</span><br></pre></td></tr></table></figure>

<p>k 个 hash 函数，该 bit 设置为 0 的概率为：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">P<span class="number">'</span>(<span class="number">0</span>) = P(<span class="number">0</span>) ** k = (<span class="number">1</span> - <span class="number">1</span>/m) ** k</span><br></pre></td></tr></table></figure>

<p>再经过 n 个 key，该 bit 设置为 0 的概率为</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">P<span class="number">''</span>(<span class="number">0</span>) = P<span class="number">'</span>(<span class="number">0</span>) ** n = (<span class="number">1</span> - <span class="number">1</span>/m) ** kn</span><br></pre></td></tr></table></figure>

<p>根据自然对数e的公式：</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041413726.png" alt=""></p>
<p>我们可以近似计算前面的<code>P&#39;&#39;(0)</code></p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041414674.png" alt=""></p>
<p>关于自然对数 e 的值，可以看下面的内容:</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041327457.png" alt=""></p>
<p>当检测某个实际不存在的 key 时，满足条件：</p>
<p>其对应的 k 个 bit 恰好都设置为了1，此时即 false positive 的场景。</p>
<p>概率为：</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041418134.png" alt=""></p>
<p>问题是，怎么最小化 false_positive 呢？</p>
<p>为了简化描述，先定义 p (即<code>P&#39;&#39;(0)</code>：某个 bit 设置为0的概率)：</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041423865.png" alt=""></p>
<p>根据公式推导：</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041424497.png" alt=""></p>
<p>底数是 e，为固定值，那么最小化 false_positive_rate 即为最小化指数</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041424841.png" alt=""></p>
<p>根据之前的计算结果，我们可以做下面的变形：</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041431847.png" alt=""></p>
<p>最终得到结果 g：</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041431129.png" alt=""></p>
<p>根据对称性，当 <code>p = 1/2</code> 时，f 取得最小值。</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041435792.png" alt=""></p>
<p>此时k、f最小值为：</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041436632.png" alt=""></p>
<p>最终的推导结果：</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041441884.png" alt=""></p>
<p>考虑到 p 为设置为0的概率，因此<strong>可以认为 m 有一半设置为1，一半设置为0时，误判率最低</strong>。</p>
<p><code>false position</code>和m/n、k 的组合关系表例子可以下面的截图：</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/202205041219187.png" alt=""></p>
<h1 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h1><p>Bloom Filter 通常用于快速判断某个元素是否在集合中。其本质上容忍一定的错误率来换取时空的高效性。</p>
<p>对于LevelDB的意义：在哈希表的基础上省下了冲突处理部分，LevelDB 在实现时使用了某种优化：<strong>利用一个哈希函数来达到近似 k 个哈希函数的效果</strong>。这样做实现了高效的并发写入同时不会牺牲过多的性能。</p>
<p>LevelDB除开哈希函数和针对并发写入的优化部分之外，其他部分都非常贴合布隆过滤器的理论基础，也是优秀的学习案例，作为C++版本的过滤器生产案例应用也是一个不错的参考范本。</p>
<p>最后，有问题找布隆准没错。</p>
<h1 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h1><p>下面的资料绝对能让你吃透布隆过滤器。</p>
<blockquote>
<p>公众号请“阅读原文”获取访问链接。</p>
</blockquote>
<ul>
<li><span class="exturl" data-url="aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tZW5nL2FydGljbGUvZGV0YWlscy8xNDk1NTAw" title="https://blog.csdn.net/jiaomeng/article/details/1495500">Bloom Filter概念和原理_jiaomeng的博客-CSDN博客_bloomfilter<i class="fa fa-external-link"></i></span></li>
<li><span class="exturl" data-url="aHR0cHM6Ly9sbGltbGxpYi5naXRodWIuaW8vYmxvb21maWx0ZXItdHV0b3JpYWwvemhfQ04v" title="https://llimllib.github.io/bloomfilter-tutorial/zh_CN/">Bloom Filters by Example (llimllib.github.io)<i class="fa fa-external-link"></i></span></li>
<li><span class="exturl" data-url="aHR0cDovL2MuYmlhbmNoZW5nLm5ldC9jcHAvYmlhbmNoZW5nL3ZpZXcvMzI5Ny5odG1s" title="http://c.biancheng.net/cpp/biancheng/view/3297.html">C++四种类型转换运算符：static_cast、dynamic_cast、const_cast和reinterpret_cast_C语言中文网 (biancheng.net)<i class="fa fa-external-link"></i></span></li>
<li><span class="exturl" data-url="aHR0cDovL3d3dy5lZWNzLmhhcnZhcmQuZWR1L35taWNoYWVsbS9wb3N0c2NyaXB0cy9lc2EyMDA2YS5wZGY=" title="http://www.eecs.harvard.edu/~michaelm/postscripts/esa2006a.pdf">LNCS 4168 - Less Hashing, Same Performance: Building a Better Bloom Filter (harvard.edu)<i class="fa fa-external-link"></i></span></li>
<li><span class="exturl" data-url="aHR0cHM6Ly9naXRodWIuY29tL2dvb2dsZS9sZXZlbGRiL2Jsb2IvbWFpbi9kb2MvaW5kZXgubWQjZmlsdGVycw==" title="https://github.com/google/leveldb/blob/main/doc/index.md#filters">leveldb/index.md at main · google/leveldb · GitHub<i class="fa fa-external-link"></i></span></li>
<li><span class="exturl" data-url="aHR0cDovL3d3dy5lZWNzLmhhcnZhcmQuZWR1L35taWNoYWVsbS9wb3N0c2NyaXB0cy9pbTIwMDViLnBkZg==" title="http://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf">im2005b.pdf (harvard.edu)<i class="fa fa-external-link"></i></span></li>
<li><span class="exturl" data-url="aHR0cDovL3d3dy5lZWNzLmhhcnZhcmQuZWR1L35taWNoYWVsbS9wb3N0c2NyaXB0cy90b24yMDAyLnBkZg==" title="http://www.eecs.harvard.edu/~michaelm/postscripts/ton2002.pdf">Compressed bloom filters - Networking, IEEE/ACM Transactions on (harvard.edu)<i class="fa fa-external-link"></i></span></li>
<li><span class="exturl" data-url="aHR0cHM6Ly9penVhbHpoeS5jbi9sZXZlbGRiLWJsb29tLWZpbHRlcg==" title="https://izualzhy.cn/leveldb-bloom-filter">leveldb笔记之9:bloom filter - Ying’s Blog (izualzhy.cn)<i class="fa fa-external-link"></i></span></li>
</ul>
<script type="text/javascript" src="https://cdn.jsdelivr.net/npm/kity@2.0.4/dist/kity.min.js"></script><script type="text/javascript" src="https://cdn.jsdelivr.net/npm/kityminder-core@1.4.50/dist/kityminder.core.min.js"></script><script defer="true" type="text/javascript" src="https://cdn.jsdelivr.net/npm/hexo-simple-mindmap@0.2.0/dist/mindmap.min.js"></script><link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/npm/hexo-simple-mindmap@0.2.0/dist/mindmap.min.css">
    </div>

    
    
    
        

<div>
<ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者： </strong>阿东
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="https://whitestore.top/2022/05/21/leveled-bloom/" title="LSM-Tree - LevelDb 布隆过滤器">https://whitestore.top/2022/05/21/leveled-bloom/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <span class="exturl" data-url="aHR0cHM6Ly9jcmVhdGl2ZWNvbW1vbnMub3JnL2xpY2Vuc2VzL2J5LW5jLzQuMC96aC1DTg=="><i class="fa fa-fw fa-creative-commons"></i>BY-NC</span> 许可协议。转载请注明出处！
  </li>
</ul>
</div>


      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/LevelDB/" rel="tag"># LevelDB</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2022/05/21/bntydkcm/" rel="prev" title="14岁懂社会-《被你讨厌的昆虫们》读书笔记">
      <i class="fa fa-chevron-left"></i> 14岁懂社会-《被你讨厌的昆虫们》读书笔记
    </a></div>
      <div class="post-nav-item">
    <a href="/2022/05/21/level-skiplist/" rel="next" title="LSM-Tree - LevelDb Skiplist跳表">
      LSM-Tree - LevelDb Skiplist跳表 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#LSM-Tree-LevelDb布隆过滤器"><span class="nav-number">1.</span> <span class="nav-text">LSM-Tree - LevelDb布隆过滤器</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#引言"><span class="nav-number">2.</span> <span class="nav-text">引言</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#理论"><span class="nav-number">3.</span> <span class="nav-text">理论</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#levelDB实现"><span class="nav-number">4.</span> <span class="nav-text">levelDB实现</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#index-md介绍"><span class="nav-number">4.1.</span> <span class="nav-text">index.md介绍</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#FilterPolicy"><span class="nav-number">4.2.</span> <span class="nav-text">FilterPolicy</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#bloom-cc"><span class="nav-number">4.3.</span> <span class="nav-text">bloom.cc</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#hash-cc"><span class="nav-number">4.4.</span> <span class="nav-text">hash.cc</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Slice-h"><span class="nav-number">4.5.</span> <span class="nav-text">Slice.h</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#其他内容"><span class="nav-number">5.</span> <span class="nav-text">其他内容</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#单元测试"><span class="nav-number">5.1.</span> <span class="nav-text">单元测试</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#c-语法"><span class="nav-number">5.2.</span> <span class="nav-text">c++语法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#数学推导"><span class="nav-number">5.3.</span> <span class="nav-text">数学推导</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#总结"><span class="nav-number">6.</span> <span class="nav-text">总结</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#参考资料"><span class="nav-number">7.</span> <span class="nav-text">参考资料</span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">阿东</p>
  <div class="site-description" itemprop="description">随遇而安</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">239</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">36</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">37</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <span class="exturl" data-url="aHR0cHM6Ly9naXRodWIuY29tL2xhenlUaW1lcw==" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;lazyTimes"><i class="fa fa-fw fa-github"></i>GitHub</span>
      </span>
      <span class="links-of-author-item">
        <span class="exturl" data-url="bWFpbHRvOjEwOTc0ODM1MDhAcXEuY29t" title="E-Mail → mailto:1097483508@qq.com"><i class="fa fa-fw fa-envelope"></i>E-Mail</span>
      </span>
  </div>


  <div class="links-of-blogroll motion-element">
    <div class="links-of-blogroll-title">
      <i class="fa fa-fw fa-link"></i>
      友情链接
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <span class="exturl" data-url="aHR0cHM6Ly93d3cuNTJwb2ppZS5jbi9ob21lLnBocD9tb2Q9c3BhY2UmdWlkPTE0OTc3MTgmZG89dGhyZWFkJnZpZXc9bWUmZnJvbT1zcGFjZQ==" title="https:&#x2F;&#x2F;www.52pojie.cn&#x2F;home.php?mod&#x3D;space&amp;uid&#x3D;1497718&amp;do&#x3D;thread&amp;view&#x3D;me&amp;from&#x3D;space">吾爱破解</span>
        </li>
        <li class="links-of-blogroll-item">
          <span class="exturl" data-url="aHR0cHM6Ly9qdWVqaW4uaW0vdXNlci8yOTk5MTIzNDUyNjI2MzY2" title="https:&#x2F;&#x2F;juejin.im&#x2F;user&#x2F;2999123452626366">掘金</span>
        </li>
        <li class="links-of-blogroll-item">
          <span class="exturl" data-url="aHR0cHM6Ly9zZWdtZW50ZmF1bHQuY29tL3UvbGF6eXRpbWVz" title="https:&#x2F;&#x2F;segmentfault.com&#x2F;u&#x2F;lazytimes">思否</span>
        </li>
    </ul>
  </div>

      </div>

      <div class="wechat_OA">
        <span>欢迎关注我的公众号</span>
        <br>
          <!-- 这里添加你的二维码图片 -->
        <img src ="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/wechat_channel.jpg">
      </div>
        <div class="back-to-top motion-element">
          <i class="fa fa-arrow-up"></i>
          <span>0%</span>
        </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2023</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">阿东</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-area-chart"></i>
    </span>
      <span class="post-meta-item-text">站点总字数：</span>
    <span title="站点总字数">2m</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
      <span class="post-meta-item-text">站点阅读时长 &asymp;</span>
    <span title="站点阅读时长">29:50</span>
</div>
  <div class="powered-by">由 <span class="exturl theme-link" data-url="aHR0cHM6Ly9oZXhvLmlv">Hexo</span> & <span class="exturl theme-link" data-url="aHR0cHM6Ly90aGVtZS1uZXh0Lm9yZw==">NexT.Gemini</span> 强力驱动
  </div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js"></script>
  <script src="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>




  




  
<script src="/js/local-search.js"></script>













  

  


<script>
NexT.utils.loadComments(document.querySelector('#valine-comments'), () => {
  NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
    var GUEST = ['nick', 'mail', 'link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item => {
      return GUEST.includes(item);
    });
    new Valine({
      el         : '#valine-comments',
      verify     : false,
      notify     : true,
      appId      : 'qMUpEEvBgXaMDD1b0ftgi9xr-gzGzoHsz',
      appKey     : 'UCdfT4Rfih6MO6y8DI4fstf6',
      placeholder: "Just go go",
      avatar     : 'mm',
      meta       : guest,
      pageSize   : '10' || 10,
      visitor    : false,
      lang       : 'zh-CN' || 'zh-cn',
      path       : location.pathname,
      recordIP   : false,
      serverURLs : ''
    });
  }, window.Valine);
});
</script>

</body>
</html>
